#include <iostream>
#include <vector>
using namespace std;
// 70. 爬楼梯
// 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
//每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
// https://leetcode.cn/problems/climbing-stairs/description/

// 递归方式-记忆化搜索
class Solution {
private:
    vector<int> memo;
    int calcWays(int n) {
        if(n == 0 || n == 1)  // n == 0表示1个台阶都没有，则1节台阶都不走，没有可能性
            return 1;
//        if(n == 2)
//            return 2;
        if(memo[n] == -1) {
            memo[n] = calcWays(n-1) + calcWays(n-2);
        }
        return memo[n];
    }
public:
    int climbStairs(int n) {
        memo = vector<int>(n+1, -1);
        return calcWays(n);
    }
};
int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
